package arithmetic.intersection;

/**
 * 相交链表:
 * 给你两个单链表的头节点 headA 和 headB ，
 * 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 * 保证 整个链式结构中不存在环。
 * 进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
 * 1、双循环 时间复杂度O(n^2) 空间复杂度O(1)
 * 2、引入hash表，时间复杂度O(n) 空间复杂度O(n)
 * 3、双指针
 * 4、先获取两个链表的长度，然后长度大的链表从差值开始循环，与长度小的链表开始比较
 *
 */
public class Test {

    public static void main(String[] args) {

    }

    /**
     * 双指针
     * 如果没有相交节点，最后相遇都是返回的null
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode getIntersectionNode1(ListNode headA,ListNode headB){
        if (headA ==null || headB ==null) return null;
        ListNode head1=headA,head2=headB;
        while (head1 != head2){
            head1=head1==null?headB:head1.next;
            head2=head2==null?headA:head2.next;
        }
        return head1;
    }

    /**
     * 第四种办法
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode getIntersectionNode(ListNode headA,ListNode headB){
        int l1=0,l2=0,diff=0;
        ListNode head1=headA,head2=headB;
        while (head1 !=null){
            l1++;
            head1=head1.next;
        }
        while (head2 !=null){
            l2++;
            head2=head2.next;
        }
        if(l1 < l2){
            diff=l2-l1;
            head2=headB;
            head1=headA;
            for (int i=0;i<diff;i++){
                head2=head2.next;
            }
        }else {
            diff=l1-l2;
            head1=headA;
            head2=headB;
            for (int i=0;i<diff;i++){
                head1=head1.next;
            }
        }
        while (head1 != null && head2!=null){
            if (head1 == head2) return head1;
            head1=head1.next;
            head2=head2.next;
        }
        return null;
    }


}

class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        val=x;
        next=null;
    }
}
